This invention relates to the processing of images such as photographs, drawings, and other two dimensional displays. It further relates to the processing of such images after they have been captured in digital format or after they have been converted to or otherwise expressed in digital format. This invention further relates to use of novel coding methods to increase the speed and compression ratio for digital image storage and transmission.
Recently subband coding has emerged as the leading standardization candidate in future image compression systems due to the development of the discrete wavelet transform (DWT). The multiresolution characteristics of the wavelet transform establish an intuitive foundation on which simple yet sophisticated methods of encoding the transform coefficients are developed. Exploiting the relationship between the parent and the offspring coefficients in wavelet tree, zerotree-based wavelet coders, for example, J. M. Shapiro, xe2x80x9cEmbedded image coding using zerotrees of wavelet coefficients,xe2x80x9d IEEE Trans. on SP, vol. 41, pp. 3445-3462, December 1993 [hereinafter EZW]; A. Said and W. A. Pearlman, xe2x80x9cA new fast and efficient image codec on set partitioning in hierarchical trees,xe2x80x9dIEEE Trans on Circuits Syst. Video Tech., vol. 6, pp. 243-550, June 1996 [hereinafter SPIHT]; and xe2x80x9cCompression with reversible embedded wavelets,xe2x80x9d RICOH Company Ltd. submission to ISO/IEC JTC1/SC29/WG1 for the JTC1.29.12 work item, 1995. http://www.crc.ricoh.com/CREW [hereinafter CREW] can effectively order the coefficients by bit planes and transmit more significant bits first. This elegant coding scheme results in an embedded bit stream (i.e., it can be truncated at any point by the decoder to yield the best corresponding reconstructed image) and many other interesting features such as exact bit rate control and idempotency capability. It became apparent that the same idea can be applied to block transform coefficients as well if these are grouped in a wavelet-like octave-band fashion, e.g., Z. Xiong, O. Guleryuz, and M. T. Orchard, xe2x80x9cA DCT-based embedded image coder,xe2x80x9d IEEE SP Letters, vol. 3, pp. 289-590, November 1996; H. Malvar, xe2x80x9cLapped biorthogonal transforms for transform coding with reduced blocking and ringing artifacts,xe2x80x9d ICASSP97, Munich, April 1997;] T. Klausutis and V. Madisetti, xe2x80x9cAdaptive lapped transform-based image coding,xe2x80x9d IEEE SP Letters, vol. 4, pp. 245-547, September 1997; T. D. Tran and T. Q. Nguyen, xe2x80x9cA lapped transform embedded image coder,xe2x80x9d ISCAS, Monterey, May 1998, as illustrated in FIG. 1. Global information is fully taken into account in these subband coders, leading to excellent performance.
However, perfect embeddedness is achieved at a high computational cost. Such embeddedness requires a full buffering of all the transform coefficients. First of all, this requirement becomes burdensome when the input images have high resolution (in desktop publishing applications for example) and/or the decoder has limited resources. Second, a full buffering with multiple passes is very costly in hardware implementation. Finally, full buffering prevents the application of powerful parallel processing techniques.
It is therefore an object of the current invention to sacrifice progressive transmission capability for a faster coder with a lower implementation complexity and a comparable quality performance. It is a further object of the current invention to construct such a coder by partitioning the transform coefficients into small local groups and encoding them independently using popular zerotree-based algorithms. It is yet a further object of this invention to provide a coder with negligible performance penalty. It is another object of this invention to provide a coder with performance almost identical to the fully embedded version when the partition size is reasonably large. It is another object of this invention to maintain embeddedness within the local groups while losing global embeddedness in the final output bitstream.
The LZT coding algorithm of this invention has at least the following fundamental steps:
1) Partitioning the input image into many local blocks. (The size of the partition is chosen based on a tradeoff between the desired level of resolution and the availability of computing resources, which determine an allowable level of implementation complexity.)
2) Transforming each partition, that is, each local block, independently using a block coder. (Some special attention is required at the partition boundaries to ensure continuity in the reconstructed image.)
3) Quantizing the coefficients in each partition by the appropriate JND thresholds or by truncating a certain number of least significant bit planes.
4) Arranging the quantized coefficients in wavelet-like quad-tree fashion as shown in FIG. 2 and encode each group separately using any zerotree coding algorithm.
5) Concatenating the bitstreams to yield the final output.
Most generally, this invention comprises the steps of partitioning the image into a plurality of local blocks, performing a block coding transform on each local block of the plurality of local blocks so as to produce a corresponding plurality of sets of local block transform coefficients using a block coding algorithm, quantizing the local block transform coefficients in each set of local block transform coefficients of the plurality of local block transform coefficients, arranging the plurality of sets of quantized local block transform coefficients in a wavelet-like quad-tree structure, and concatenating the bit-streams of the encoded quantized coefficients from each of the plurality of local blocks.